Many communications systems currently use encryption to enhance security of the systems. These communication systems include but are not limited to communication systems, such as, personal communication systems, paging systems, cellular phone systems, cable systems, as well as other private and public cable, wireline, and wireless voice or data networks. By way of example a typical communication system will be described below; however, it will be appreciated by those skilled in the art that the encryption techniques described can be readily extended to other communication systems without departing from the scope and spirit of the present invention.
Turning now to the typical communication systems, these systems usually include subscriber units (such as mobile, cable boxes, or portable units) which communicate with a fixed network communication unit via communication links. In such communication systems, the communication link is the primary target for cryptographic systems, because it is the most vulnerable to unauthorized introduction (spoofing) or extraction (eavesdropping) of information. It is well known in the art that information in these communication links may be cryptographically protected by encrypting them with a pseudonoise (PN) signal which is pseudo-random in nature. For example this may be accomplished by performing an exclusive-or operation of an information signal with a PN signal, prior to transmission. Subsequently, the inverse operation can be performed during the receiving process.
The PN signals are not truly random, but appear random when subject to cursory inspection. The advantage of these PN signals is that they can be easily generated by a linear feedback shift register (LFSR). An LFSR generates a PN signal which is periodic and deterministic. The periodicity of the PN signal is dependent on the number of stages (i.e., bits stored) in the register, the feedback "taps", and the initial state of the LFSR stages. The LFSR implements an Nth degree polynomial (where N is the number of stages of the LFSR) by having one feedback signal "tap" (output bit of a stage) for each coefficient of the polynomial. An input bit is formed from an exclusive-or operation on the outputs or selected outputs of these feedback signal "taps" and fed back into the register. Ideally feedback "taps" can be chosen which implement a maximal length PN signal generator. A maximal length PN generator generates a pseudo-random sequence which repeats every 2.sup.N -l cycles, where N is the number of stages in the register. Examples of maximal length feedback tap arrangements for several different stage length registers are given in "Error-Correcting Codes", second edition by W. Wesley Peterson and E. J. Weldon, Jr., MIT Press, 1972.
The problem with using this form of PN generators to cryptographically protect an information signal is that they are extremely vulnerable to attack (i.e., the encryption is easy to crack or break). The weakness of PN generators which are based on an LFSR is primarily due to the inherent linearity of the generators. Since PN generators operate according to an algorithm, knowledge of the algorithm reveals the entire sequence. Further, as noted in chapter 5 of "Cipher Systems" by Henry Baker and Fred Piper, Northwood Publications, 1992, a cryptoanalyst needs only 2N bits of plaintext and corresponding ciphertext for an N stage long LFSR to be able to determine the feedback "taps", the initial state of the LFSR, and ultimately any PN signal output by the LFSR. This vulnerability represents a major drawback to the continued use of the LFSR to cryptographically protect communication systems.
To address this vulnerability various forms of introducing non-linearity into the basic LFSR structure have been discussed. Two such discussions, both assigned to the same assignee as here and incorporated herein by reference, are 1) U.S. Pat. No. 5,060,265 by Finkelstein issued on Oct. 22, 1991 and titled Method Of Protecting A Linear Feedback Shift Register (LFSR) Output Signal" and 2) U.S. Pat. No. 5,365,585 by Puhl et al. issued on Nov. 15, 1994 and titled "Method And Apparatus For Encryption Having A Feedback Register With Selectable Taps". While either reference teaches an approach for improving cryptographic protection practitioners continue to require additional protection and encryption processors having higher cryptographic throughput.
Another class of PN generator is the linear congruential generator (LCG). An LCG has the form:
x(n+1)={a*x(n)+b} mod c, where; the constants a, b, c are defined as PA1 a=the multiplier, PA1 b=the increment, PA1 c=the modulus, PA1 x(0) is the first (given) value in the sequence.
The sequence generated is then the values x(0), x(1), x(2), . . . Since LCGs are linear they are also vulnerable to cryptographic attack for the same or similar reasons cited regarding LFSRs.
Therefore, a need continues to exist for improved encryption protection techniques for communication systems, which techniques may alleviate these problems.